﻿#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include <thread>
#include <unordered_map>
#include <mutex>
using std::cout;
using std::endl;
//该文件被多次包含，需要加上static
static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREE_LISTS = 208;
static const size_t NPAGES = 129; //0号浪费掉，[1,128]
static const size_t PAGE_SHIFT = 13; //这里在一页为8KB时，有2^13次方B
//32位只有_WIN32,64位_WIN32和_WIN64都有
#ifdef  _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#else 
	//linux...
#endif


#ifdef _WIN32
#include <windows.h>
#else
//linux下的头文件
#endif

// 直接去堆上按页申请空间 
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	//一页是8K，这里是申请多少页的内存
	void* ptr = VirtualAlloc(0, kpage * 8 * 1024, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等 
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	//linux
#endif
}


static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

//管理切分好的小对象自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		assert(obj);
		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	void* Pop()
	{
		//头删
		assert(_freeList);
		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		--_size;
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}

	void PushRange(void* start, void* end, size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;

		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freeList;
		end = start;
		//走n-1步即可，end指向最后一个，而不是最后一个的下一个
		for (size_t i = 0; i < n - 1; i++)
		{
			end = NextObj(end);
		}
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};


//计算对象大小的对齐映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费 0
	// [1,128]					8byte对⻬		freelist[0,16) 
	// [128+1,1024]				16byte对⻬		freelist[16,72) 
	// [1024+1,8*1024]			128byte对⻬		freelist[72,128) 
	// [8*1024+1,64*1024]		1024byte对⻬		freelist[128,184) 
	// [64*1024+1,256*1024]		8*1024byte对⻬	freelist[184,208)
	// version 1
	//size_t _RoundUp(size_t size, size_t alignNum)
	//{
	//	size_t alignSize;
	//	if (size % alignNum != 0)
	//	{
	//		alignSize = (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		alignSize = size;
	//	}
	//	return alignSize;
	//}
	// version 2
	//利用这个增速，与我们要申请的字节数，算出一个浪费最小的内存块
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
	}
	//我们申请的内存一般都是一个随机的整数，
	//我们需要先将其对齐一下，使得这个内存块的大小刚好在链表中能找到，允许一小部分的内部碎片，只要方便我们拿内存块即可
	//如要9字节开16字节, 要129字节开144字节，要67k开72kB
	static inline size_t RoundUp(size_t bytes)
	{
		if (bytes <= 128)
		{
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024)
		{
			return _RoundUp(bytes, 16);
		}
		else if (bytes <= 8 * 1024)
		{
			return _RoundUp(bytes, 128);
		}
		else if (bytes <= 64 * 1024)
		{
			return _RoundUp(bytes, 1024);
		}
		else if (bytes <= 256 * 1024)
		{
			return _RoundUp(bytes, 8 * 1024);
		}
		else
		{
			//assert(false);
			return _RoundUp(bytes, 1 << PAGE_SHIFT);
		}
	}



	//计算映射的是哪一个自由链表桶
	//version 1
	// 如这里的alignNum直接就是8，不需要转换
	//static inline size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum == 0)
	//	{
	//		return bytes / alignNum - 1;
	//	}
	//	else
	//	{
	//		return bytes / alignNum;
	//	}
	//}
	//version 2
	//alignNumShift 是 alignNum的转换，它的次方数，如8-->3
	static inline size_t _Index(size_t bytes, size_t alignNumShift)
	{
		return ((bytes + (1 << alignNumShift) - 1) >> alignNumShift) - 1;
	}
	//算一下这么大小的内存应该从几号链表中去拿
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);
		//每一个内存增速有多少个内存块
		static int group_array[4] = { 16 , 56, 56 , 56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			//这里要减去128，是因为前128B时增速与这里不一致，是一个分段函数，只要我们最后把增长到128的所需要消耗的“时间”给加上即可
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[1] + group_array[0];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[2] + group_array[1] + group_array[0];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[3] + group_array[2] + group_array[1] + group_array[0];
		}
	}
	//一次thread_cache 从中心缓存获取多少个
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		//控制在[2, 512]范围内
		//小对象一次批量上限高，小对象一次批量上限低
		int num = MAX_BYTES / size;
		if (num < 2)
		{
			num = 2;
		}
		if (num > 512)
		{
			num = 512;
		}
		return num;
	}
	//计算一次向系统获取几个页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size); //threadcache一次要多少个size
		size_t npage = num * size; //字节数

		npage >>= PAGE_SHIFT; //这些字节数相当于多少页
		if (npage == 0)
		{
			npage = 1; //最低也得一页
		}
		return npage;
	}
};
//管理多个连续页的大块内存跨度结构
struct Span
{
	PAGE_ID _pageId = 0; //页号
	size_t _n = 0; //页的数量

	//双向链表指针
	Span* _next = nullptr; 
	Span* _prev = nullptr;

	size_t _objSize = 0; //切好的小对象的大小，只需要一个对象的大小，因为ptr指针可以转换为span页号，从而映射找到span大小
	size_t _useCount = 0; //切好的小块内存，被分配给thread_cache的计数
	void* _freeList = nullptr; //切好的小块内存的自由链表

	bool _isUse = false; //是否在被使用
};

//带头双向循环链表
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* front = _head->_next;
		Erase(front);
		return front;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);
		Span* prev = pos->_prev;
		Span* next = pos->_next;
		prev->_next = next;
		next->_prev = prev;
		//对于central cache层，这个pos不需要delete掉，而是要还给下层PageCache
		//对于page cache层，这个pos不需要delete掉，而是断开链接交给上层central cache层
	}
private:
	Span* _head;
public:
	std::mutex _mtx; //桶锁，每一个Span链表都要有一个锁
};